/*
 * Graph.cpp
 *
 *  Created on: 11 oct. 2011
 *      Author: amothe
 */

#include <sstream>
#include "Graph.h"

Graph::Graph() {
	_vertex_list = vector<vector<int> >();
}

Graph::Graph(vector<vector<int> > src) {
	_vertex_list = src;
}

Graph::~Graph() {
}

int Graph::addVertex() {
	_vertex_list.push_back(vector<int>());
	return _vertex_list.size() - 1;
}

void Graph::addEdge(int vertex, int vertex2) {
	_vertex_list[vertex].push_back(vertex2);
	_vertex_list[vertex2].push_back(vertex);
}

void Graph::delEdge(int vertex1, int vertex2) {
	vector<int> tmp1 = _vertex_list[vertex1];
	vector<int> tmp2 = _vertex_list[vertex2];

	for (int i = 0; i < tmp1.size(); i++) {
		if (tmp1[i] == vertex2) {
			_vertex_list[vertex1].erase(_vertex_list[vertex1].begin() + i);
			break;
		}
	}

	for (int i = 0; i < tmp2.size(); i++) {
		if (tmp2[i] == vertex1) {
			_vertex_list[vertex2].erase(_vertex_list[vertex2].begin() + i);
			break;
		}
	}
}

int Graph::numEdge(int vertex) const {
	return _vertex_list[vertex].size();
}

bool Graph::haveEdge(int vertex1, int vertex2) {
	for (int i = 0; i < _vertex_list[vertex1].size(); i++)
		if (_vertex_list[vertex1][i] == vertex2)
			return true;
	return false;
}

string Graph::toString() {
	std::ostringstream s;
	for (unsigned int i = 0; i < _vertex_list.size(); i++) {
		s << i + 1 << ":";
		for (unsigned int j = 0; j < _vertex_list[i].size(); j++) {
			s << " " << _vertex_list[i][j] + 1;
		}
		s << "\n";
	}
	return s.str();
}

int Graph::getVertexNeighbour(int vertex, int index) const {
	return _vertex_list[vertex][index];
}

vector<int> Graph::getNeighbours(int vertex) const {
	vector<int> copy;
	for (int i = 0; i < _vertex_list[vertex].size(); i++) {
		copy.push_back(_vertex_list[vertex][i]);
	}
	return copy;
}

int Graph::getNbVertex() const {
	return _vertex_list.size();
}

void Graph::delVertex(int vertex) {
	vector<int> tmp = _vertex_list[vertex];
	for (int i = 0; i < tmp.size(); i++) {
		delEdge(vertex, tmp[i]);
	}
}

Graph *
Graph::copy() const {
	Graph *copy = new Graph();
	for (int i = 0; i < _vertex_list.size(); i++) {
		copy->addVertex();
	}

	for (int i = 0; i < _vertex_list.size(); i++) {
		for (int j = 0; j < _vertex_list[i].size(); j++) {
			if (!copy->haveEdge(i, _vertex_list[i][j])) {
				copy->addEdge(i, _vertex_list[i][j]);
			}
		}
	}
	return copy;
}

